﻿using System;

class BinaryDigitsCountNew
{
    static void Main()
    {
        //C# Fundamentals 2011/2012 Part 1 - Sample Exam

        byte digitB = byte.Parse(Console.ReadLine());
        ushort N = ushort.Parse(Console.ReadLine());     //USHORT - за да обхване от 1 до 1000

        for (int i = 0; i < N; i++)
        {
            uint currentNumber = uint.Parse(Console.ReadLine());

            int count = 0;
            while (currentNumber != 0)
            {
                if ((currentNumber & 1) == digitB)
                {
                    count++;
                }
                currentNumber = currentNumber >> 1;
            }
            Console.WriteLine(count);
        }


    }
}

